package book;

public class KMPSolution {
    // 简单的暴力匹配方法
    int search(String s, String p) {
        int n = 0;
        for (int i = 0; i < s.length() - p.length(); i++) {
            boolean match = true;
            for (int j = 0; j < p.length(); j++) {
                if (s.charAt(i + j) != p.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                System.out.println("匹配位置：" + i);
                n++;
            }
        }
        System.out.println("共找到" + n + "个结果");
        return n;
    }
    
    // KMP算法实现：构建next数组
    int[] buildNext(String s) {
        int[] next = new int[s.length()];
        next[0] = -1;
        for (int i = 1; i < s.length(); i++) {
            int nexti = next[i - 1] + 1;
            while (nexti >= 0 && s.charAt(nexti) != s.charAt(i))
                nexti = nexti > 0 ? next[nexti - 1] + 1 : -1;
            next[i] = nexti;
        }
        return next;
    }

    // 使用KMP算法进行字符串匹配
    int searchKMP(String s, String p) {
        int[] next = buildNext(p);
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            while (j >= 0 && s.charAt(i) != p.charAt(j)) {
                if (j == 0) 
                    j = -1;
                else
                    j = next[j - 1] + 1;
            }
            if (++j == p.length())
                return i - j + 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        String s = "ababaababcb", p = "ababc";
        int ans = new KMPSolution().searchKMP(s, p);
        System.out.println("匹配的下标位置为: " + ans);
    }
}

